Conventionally, a CRC (“Cyclic Redundancy Check”) code is used to detect erroneous bits in the information transmitted between two systems, namely a source system (emitter) and one or more receiving systems (receivers).
The emitter and the receivers are coupled by transmission circuitry that is usually not very reliable, which may disrupt the content of the information transmitted. For example, an information word being written in the form of a bit sequence “100011011” may, on reception, become “001011011”. The values of the first and third bits have been corrupted during transmission.
For the receivers to detect that the received information word is incorrect, a few bits called the “signature” are added to the information word. This signature is obtained by applying a hash function to the information word to be transmitted, such as:H(MI)=CRC Where H is the hash function, MI is an information word to be transmitted, and CRC is its signature. This hash function is commonly called “Checksum” by those skilled in the art.
There are many functions capable of generating the signature (like the add function). Such a checksum function is considered to be effective if the signature systematically indicates the appearance of an erroneous bit.
An example checksum function is called Euclidian division. More precisely, the signature, also called “redundancy”, is generated by dividing the information word to be transmitted by a generator polynomial. The redundancy is then equal to the rest of this Euclidian division.
It is considered that a generator polynomial supplies an effective redundancy if the latter allows the detection of a maximum of erroneous bits in the received information word. The qualification of a good generator polynomial then depends on the types of the most frequent errors associated with the transmission circuitry. Mainly, there are two types of errors, namely independent random errors (according to the Bernouilli scheme) and burst errors, in other words a certain number of consecutive erroneous bits.
It is particularly difficult to find a generator polynomial capable of generating a redundancy allowing the detection of these errors, whether they be random or burst.